/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
// 递归
// 二叉搜索树左节点不能等于根节点!!!
// time: O(n), space: O(logn)
func isValidBST(root *TreeNode) bool {
	return helper(root, math.MinInt64, math.MaxInt64)
}

// 递归判断是否为二叉搜索树
// 1. 左节点 < root < 右节点
// 2. 左子树，右子树分别递归满足条件1
func helper(root *TreeNode, lower, upper int) bool {
	if root == nil {
		return true
	}

	if lower >= root.Val || root.Val >= upper {
		return false
	}

	return helper(root.Left, lower, root.Val) && helper(root.Right, root.Val, upper)
}